public class HashTable {
    // 节点类
    static class Entry {
        int hash; // 哈希码
        Object key; // 键
        Object value; // 值
        Entry next;

        public Entry(int hash, Object key, Object value) {
            this.hash = hash;
            this.key = key;
            this.value = value;
        }
    }

    Entry[] table = new Entry[16];
    int size = 0; // 元素个数
    float loadFactor = 0.75f; // 12 阈值
    int threshold = (int) (loadFactor * table.length);

        /*求模运算替换为位运算
        - 前提:数组长度是2的n次方
        - hash % 数组长度等价于hash & (数组长度-1)
        2^n-1是n位全为1,所以位运算只保留最低的n位 */

    // 根据hash码获取value
    Object get(int hash, Object key) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        Entry p = table[idx];
        while (p != null) {
            if (p.key.equals(key)) {
                return p.value;
            }
            p = p.next;
        }
        return null;
    }

    // 向hash表存入新key value,如果key重复,则更新value
    void put(int hash, Object key, Object value) {
        int idx = hash & (table.length - 1);
        // 1.idx有空位 直接新增
        if (table[idx] == null) {
            table[idx] = new Entry(hash, key, value);
        } else {
            // 2.idx无空位 沿链表查找 有重复key更新 否则新增
            Entry p = table[idx]; // 头节点
            while (true) {
                if (p.key.equals(key)) {
                    p.value = value; //更新
                    return;
                }
                if (p.next == null) {
                    break;
                }
                p = p.next;
            }
            p.next = new Entry(hash, key, value); //新增
        }
        size++; // 由于更新直接return,所以可将size++提取至此
        if (size > threshold) {
            resize();
        }
    }

    // 扩容处理
    private void resize() {
        Entry[] newTable = new Entry[table.length << 1]; // 左移一位*2
        for (int i = 0; i < table.length; i++) {
            Entry p = table[i]; // 拿到每个链表头
            if (p != null) {
                //拆分链表,移动到新数组
        /*拆分规律
        一个链表最多拆成两个
        hash & table.length == 0 的一组
        hash & table.length != 0 的一组
                p
                0->8->16->24->32->40->48->null

                            a
                0->16->32->48->null

                        b
                8->24->40
                       */
                Entry a = null;
                Entry b = null;
                Entry aHead = null;
                Entry bHead = null;
                while (p != null) {
                    if ((p.hash & table.length) == 0) {
                        if (a != null) {
                            a.next = p;
                        } else {
                            aHead = p;
                        }
                        // 分配到a
                        a = p;
                    } else {
                        if (b != null) {
                            b.next = p;
                        } else {
                            bHead = p;
                        }
                        // 分配到b
                        b = p;
                    }
                    p = p.next;
                }
                // 规律: a链表保持索引位置不变,b链表索引位置+table.length
                if (a != null) {
                    a.next = null;
                    newTable[i] = aHead;
                }
                if (b != null) {
                    b.next = null;
                    newTable[i + table.length] = bHead;
                }
            }
        }
        table = newTable;//新数组代替旧数组
        threshold = (int) (loadFactor * table.length);
    }

    // 根据hash码删除,返回删除的value
    Object remove(int hash, Object key) {
        int idx = hash & (table.length - 1);
        if (table[idx] == null) {
            return null;
        }
        Entry p = table[idx];
        Entry prev = null;
        while (p != null) {
            if (p.key.equals(key)) {
                // 找到了删除
                if (prev == null) {
                    // 删除头节点
                    table[idx] = p.next;
                } else {
                    prev.next = p.next;
                }
                size--;
                return p.value;
            }
            prev = p; // 记录上一个节点
            p = p.next;
        }
        return null;
    }
}